%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Module summary
%%
%% Main authors: Olle
%% Progress to usefulness: 80%
%%
%% Implementation of a single Chord node. 
%% The Chord node ONLY takes care of the lookup function
%% (mapping keys to nodes)
%% and the synchronization of lookup state (finger tables etc).
%%
%% Uses a special message passing protocol that will be 
%% replaced/refined later.
%%
%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%    INTERFACE
%%
%% Spawn a Chord node:
%%  Either of these:
%%  NodePid = chord:create_node().
%%  NodePid = chord:create_node(InitialPosition).
%%  NodePid = chord:create_node(InitialPosition, N2).
%%
%%  Where InitialPosition is the initial position on the Chord 
%%  identifier ring, 
%%  NodePid is the Erlang process identifier of the Chord node,
%%  and N2 is an already existing chord node. 
%%
%% Look up what node is responsible for a value:
%%  Query = {find_responsible_node, KeyPosition).
%%  Reply := Value
%%
%% Send a query to a Chord node using the server interface library:
%%  CallerPid = self(),
%%  Reply = serveriface:rem_query(CallerPid, NodePid, Query).
%%
%% Send a query to a Chord node using message passing:
%%  CallerPid = self(),
%%  NodePid ! {CallerPid, Query}.
%%
%%  ReplyMsg := {NodePid, ReplyMsgPart}
%%  ReplyMsgPart := {return, Reply} | {error, ErrorMsg}
%%
%% Send a call to a Chord node using the server interface library:
%%  CallerPid = self(),
%%  Status = serveriface:rem_call(CallerPid, NodePid, Call).
%%  Status := ok
%%
%% Send a call to a Chord node using message passing:
%%  CallerPid = self(),
%%  NodePid ! {CallerPid, Call}.
%%
%%  ReplyMsg := {NodePid, ReplyMsgPart}
%%  ReplyMsgPart := ok | {error, ErrorMsg}
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


-module(chord_old).
-compile(export_all).

%%%%%%%%%%%%%%%%%%%%%%
%%
%% State object:
%%
%% {
%%   Identity        :: Node,
%%   Finger table    :: [ Node ],
%%   Successor       :: Node,
%%   Predecessor     :: Node
%% }
%%
%% Finger table:
%%
%% [
%%   finger[1],   :: Node
%%   finger[2],   :: Node
%%   ...
%% ]
%%
%% Node object:
%%
%% {
%%   Position  :: Int,
%%   Name      :: String
%%   Ip        :: String,
%%   TcpPort   :: Int
%% }
%%
%%
%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Record definitions
%%
%%%%%%%%%%%%%%%%%%%%%%%%%

-record(node,
 {
  position  = 0,   %% :: Int
  name      = "",  %% :: String
  ip        = "",  %% :: String
  port      = 0    %% :: Int
 }).

-record(state,
 {
   identity     = #node{},
   finger_table = [],      %% :: [ #node ]
   successor    = #node{},
   predecessor  = #node{}
 }).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Local functions for managing the state object
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Creates the finger table for the first node, by 
%% setting all fingers to the identity node. 
fill_finger_table(Id) ->
  lists:duplicate(get_M(), Id).

%% Get the node for the ith finger in the finger table for node n.
get_finger(Number, State) ->
  Ft = State#state.finger_table,
  lists:nth(Number, Ft).

%% Set the node for the ith finger in the finger table for node n.
%% Returns the updated state. 
set_finger(Number, Finger, State) ->
  Ft1 = State#state.finger_table,
  Ft2 = lists:set_nth(Number, Finger, Ft1),
  State#state{finger_table = Ft2}.

get_position(State) ->
  (State#state.identity)#node.position.
get_name(State) ->
  (State#state.identity)#node.name.
get_ip(State) ->
  (State#state.identity)#node.ip.
get_port(State) ->
  (State#state.identity)#node.port.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Networking help functions
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% These functions are wrappers that uses 
%% serveriface functions on State and Node.
rem_query(State, Node, Msg) ->
  serveriface:rem_query(get_name(State), Node#node.name, Msg).

rem_call(State, Node, Msg) ->
  serveriface:rem_call(get_name(State), Node#node.name, Msg).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Local functions for logic, 
%% independent of state and identity
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Get the "bit depth" of the Chord identifier ring. 
%% Determines an upper limit on the number of nodes. 
get_M() -> 4.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Local functions for logic, 
%% dependent on state and identity
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Calculates n.finger[k].start for the node n. 
finger_start(K, State) ->
  case (K < 1) or (K > get_M()) of
    true  -> error("Invalid finger index input to finger_start");
    false -> 
         N = get_position(State),
         (N + math:pow(2, K - 1)) rem math:pow(2, get_M())
  end.

%% Finds the finger from the finger table that precedes the
%% identifier Id, and is closest to Id. 
closest_preceding_finger(Id, State) ->
  test_closest_preceding_finger(get_M(), Id, State).

test_closest_preceding_finger(0, _, State) ->
  State#state.identity;
test_closest_preceding_finger(I, Id, State) ->
  Fin = get_finger(I, State),
  Fnp = Fin#node.position,
  Stp = get_position(State),
  case (Stp < Fnp) and (Fnp < Id) of
    true  -> Fin;
    false ->
      test_closest_preceding_finger(I - 1, Id, State)
  end.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Functions for logic, 
%% depending on node interaction
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% With the help of the other nodes, find the immediate 
%% successor node to the identifier Id. 
find_successor(Id, State) ->
  N2 = find_predecessor(Id, State),
  rem_query(State, N2, {get_successor}).

%% With the help of the other nodes, find the immediate 
%% predecessor node to the identifier Id. 
find_predecessor(Id, State) ->
  N2 = State#state.identity,
  test_find_predecessor(N2, Id, State).

test_find_predecessor(N2, Id, State) ->
  Suc = rem_query(State, N2, {get_successor}),
  N2p = N2#node.position,
  Sucp = Suc#node.position,
  case (N2p < Id) and (Id =< Sucp) of
    true  -> N2;
    false ->
      N22 = rem_query(State, N2, {closest_preceding_finger, Id}),
      test_find_predecessor(N22, Id, State)
  end.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Functions for creating the node and state,
%% and for updating the state. 
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Spawns a new node process with an empty state. 
%% Returns the process identifier. 
%% The process must be sent initialization commands to do 
%% anything useful.
create_node() ->
  spawn(fun() -> start_running_node(0, nothing) end).

%% Spawns a new node process and assigns it to the 
%% position Pos on the identifier circle. 
create_node(Pos) ->
  spawn(fun() -> start_running_node(Pos, nothing) end).

%% Spawns a new node process and assigns it to the 
%% position Pos on the identifier circle. 
%% Also tells the new node about the already existing node N2.
create_node(Pos, N2) ->
  spawn(fun() -> start_running_node(Pos, N2) end).

%% Spawn a new node. This part is run in the child process, 
%% and should never be run by any parent. 
start_running_node(Pos, N2) ->
  Self = #node{ position = Pos, name = self() },
  State = #state{ identity = Self },
  io:fwrite("Node ~p has been spawned.~n", [ Self#node.name ]),
  case N2 of
    nothing ->
      chord_node(State);
    _ ->
      State2 = join(N2, State),
      chord_node(State2)
  end.

%% Assigns a position to a Chord node. 
%% Returns the updated state. 
assign(Pos, State) ->
  Self  = State#state.identity,
  Self2 = Self#node{ position = Pos },
  State#state{ identity = Self2 }.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Functions for joining the identifier circle.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Tell node n that it has joined the ring, 
%% and that node n' already is present in the ring. 
%% n' is 'nothing' if the ring is empty. 
%%
%% Returns the updated state. 
%%
%% Let n learn about it's surroundings, build its state,
%% and tell other nodes about its presence. 
join(N2, State) ->
  case N2 of
    nothing ->
        Id = State#state.identity,
        Ft2 = fill_finger_table(Id),
        State#state{finger_table = Ft2, predecessor = Id};
    _ ->
        State2 = init_finger_table(N2, State),
        update_others(State2),
        State2
  end.

%% Initialize the finger table for node n, given that we already
%% know that node n' is in the Chord ring. 
%% Returns the updated state. 
init_finger_table(N2, State) ->
  Id  = State#state.identity,

  %% Find the first finger node, and save to the finger table.
  Fs  = finger_start(1, State),
  Suc = rem_query(State, N2, {find_successor, Fs}),
  State2 = set_finger(1, Suc, State),

  %% Find the predecessor to our first finger, 
  %% and make this our predecessor.
  Pred = rem_query(State, Suc, get_predecessor),
  State3 = State2#state{ predecessor = Pred },

  %% Set the successor's predecessor to our node.
  rem_call(State, Suc, {set_predecessor, Id}),

  init_fingers_i(1, N2, State3).

%% Recurse into the finger table, and set up each entry. 
%% Returns the updated state. 
init_fingers_i(I, N2, State) ->
  case I >= get_M() of
    true  -> State;
    false ->
        State2 = init_finger_i(I, N2, State),
        init_fingers_i(I + 1, N2, State2)
  end.

%% Set up a single finger table entry. 
%% Returns the updated state. 
init_finger_i(I, N2, State) ->
  case I >= get_M() of
    true  -> error("init_finger: Invalid finger number");
    false ->
        SelfPos   = get_position(State),
        NextStart = finger_start(I + 1, State),
        Fing      = get_finger(I, State),
        FingPos   = Fing#node.position,
        case (SelfPos =< NextStart) and (NextStart < FingPos) of
          true  ->
              set_finger(I + 1, Fing, State);
          false ->
              NextFing = rem_query(State, N2, {find_successor, NextStart}),
              set_finger(I + 1, NextFing, State)
        end
  end.

%% Tell other nodes about node n's presence in the Chord ring. 
%% Does not affect our state, and does not return any state. 
update_others(State) ->
  update_others_i(1, State).

%% Recurse and tell the remaining other nodes 
%% about node n's presence in the Chord ring. 
%% Does not affect our state, and does not return any state. 
update_others_i(I, State) ->
  case I > get_M() of
    true  -> State;
    false ->
        update_other_i(I, State),
        update_others_i(I + 1, State)
  end.

%% Tell a single other node about node n's presence in the Chord ring. 
%% Does not affect our state, and does not return any state. 
update_other_i(I, State) ->
  case I > get_M() of
    true  -> error("update_other_i: Invalid index");
    false ->
        Id   = State#state.identity,
        NPos = Id#node.position,
        Pos  = NPos - math:pow(2, I - 1),
        P    = find_predecessor(Pos, State),
        rem_call(State, P, {update_finger_table, Id, I})
  end.

%% We have been notified of node S's presence in the Chord ring. 
%% Node S is a candidate for our Ith finger table entry. 
%% Investigate if S should be our new finger or not. 
%% If yes, pass this information on. 
%%
%% Returns the updated state. 
update_finger_table(S, I, State) ->
  NPos = get_position(State),
  SPos = S#node.position,
  Fing = get_finger(I, State),
  FingPos = Fing#node.position,
  case (NPos =< SPos) and (SPos < FingPos) of
    true  ->
        State2 = set_finger(I, S, State),
        P = State#state.predecessor,
        rem_call(State, P, {update_finger_table, S, I}),
        State2;
    false -> State
  end.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Server loop
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Server loop. Not to be used directly, use create_node() instead.
chord_node(State) ->
  Self = get_name(State),
  receive
  {Caller, Msg} ->
    io:fwrite("Node ~p at ~B received msg { ~p , ~s } ~n",
              [Self, get_position(State), Caller, io_lib:write(Msg)]),
    case Msg of

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Actions to be called from the upper layers
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      {assign, Pos} ->
        State2 = assign(Pos, State),
        serveriface:rem_return_ok(Self, Caller),
        chord_node(State2);
      {join, N2} ->
        State2 = join(N2, State),
        serveriface:rem_return_ok(Self, Caller),
        chord_node(State2);
      {find_responsble_node, Id} ->
        N = find_successor(Id, State),
        serveriface:rem_return(Self, Caller, N),
        chord_node(State);
      get_status ->
        serveriface:rem_return(Self, Caller, State),
        chord_node(State);
      ping ->
        serveriface:rem_return_ok(Self, Caller),
        chord_node(State);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Actions to be called from other Chord nodes
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      get_successor ->
        Suc = State#state.successor,
        serveriface:rem_return(Self, Caller, Suc),
        chord_node(State);
      get_predecessor ->
        Pred = State#state.predecessor,
        serveriface:rem_return(Self, Caller, Pred),
        chord_node(State);
      {set_predecessor, Pred} ->
        State2 = State#state{ predecessor = Pred },
        serveriface:rem_return_ok(Self, Caller),
        chord_node(State2);
      {update_finger_table, S, I} ->
        State2 = update_finger_table(S, I, State),
        serveriface:rem_return_ok(Self, Caller),
        chord_node(State2);
      {find_successor, Id}  ->
        Suc = find_successor(Id, State),
        serveriface:rem_return(Self, Caller, Suc),
        chord_node(State);
      {closest_preceding_finger, Id} ->
        Fin = closest_preceding_finger(Id, State),
        serveriface:rem_return(Self, Caller, Fin),
        chord_node(State);

      _ ->
        Emsg = "chord_node: Unsupported message type received.",
        io:fwrite(Emsg),
        io:fwrite("~n"),
        serveriface:rem_return_error(Self, Caller, Emsg),
        chord_node(State)
    end
  end.

